It is common practice to off-load some of the computing burden of a computing device's central processing unit (CPU) to one or more, specialized co-processors, such as for performing floating-point arithmetic or input-output (I/O) routines while the CPU attends to other matters. Even mobile devices, such as smartphones and tablet computers, are seeing a rise in such parallelism.
In particular, a graphics processing unit (GPU) is programmable hardware specifically designed to perform certain routines needed to render graphics on a visual display. The term “graphics” is used in this disclosure for still or animated images that are computer-generated rather than captured by a digital camera or scanner. More importantly, they are vector graphics, a term of art used in contrast with raster graphics, which include digital images (such as JPEGs), videos (such as MPEGs), and bitmapped icons (such as GIFs), which are stored in a compressed form that can be reconstructed by decompressing. Vector graphics are stored in the form of a “model,” which is more akin to a specification as to how to generate the image to be displayed; they can typically be scaled larger, without resulting in the pixilated effect that is well known to occur when a photographic image is enlarged significantly beyond its original dimensions.
A graphics model is typically created by means of a graphics design program. The model may include a sequence of commands in a scripting language (such as SVG). At an intuitive level, these are instructions such as: draw a point at <x1,y1>; draw a line from <x2,y2> to <x3,y3>; move to <x4,y4>; draw a Bézier curve with control sequence <x5,y5>, <x6,y6>, <x7,y7>, <x8,y8>. Of course, other information, such as colours, is encoded as well. The user of a graphics design program usually does not write these instructions in the scripting language. Rather, he or she uses a WYSIWYG interface to design the graphics. For example, the interface often provides a user-friendly way to shape a Bézier curve by dragging its control points. The encoded instructions are then generated by the design program.
GPUs and the software that instructs their operation have co-evolved to handle the massive amount of computation needed to create and render graphics. A notable aspect of this co-evolution is the central role triangles have come to play in rendering. As meant herein, a “triangle” is a two-dimensional (2-D) region bounded by and including the three edges that comprise what is usually termed a “triangle” in geometry. A GPU can employ its own parallelism to render all the pixels in a triangle much more efficiently than a general-purpose CPU could; this is especially important for mobile devices dependent on battery power, as greater efficiency in rendering allows greater efficiency in power usage. In particular, if certain colour, texture, and other attributes are assigned to the vertices of a triangle, the GPU can linearly interpolate these attributes across the whole triangle very rapidly. Three-dimensional (3-D) scenes can be modelled in terms of many triangles; specifications for the model are stored in a computer graphics file. An applications programmer interface (API) provides a high-level language for communicating the graphics model to the GPU. Popular APIs, such as the OpenGL API or the DirectX API, are designed to handle 3-D graphics, but are used for 2-D graphics, as well. A program, such as a shader program, can execute on the GPU by means of an API.
GPU-driving APIs typically prohibit recursion, as it would preclude parallelization of computations, nullifying the advantages of using a dedicated GPU. This has profound implications for the rendering of curves. A classic, top-down approach to approximating a curve is to break it down into smaller and smaller pieces, until each piece can be adequately approximated by a line segment; similarly, regions on either side of the curve would be recursively broken down into finer and finer triangles. This classical approach of determining geometry on the fly cannot be adapted to the GPUs and APIs of concern herein. What GPUs and APIs need—prior to execution—is specific information about the geometry to be rendered.
Any curve can be defined in more than one way. As a toy example, the parabola in the xy-plane defined by y=f(x)=x2 can be also defined by the parametric equation f(t)=<t, t2>. Alternatively, the same set of points in plane can be specified by the implicit function f(x,y)=y−x2; this implies where the curve is in that the points <x, y> on the curve are precisely those that satisfy f(x, y)=0. The parametric function meshes well with the classical approach to approximating curves: If the curve is defined by f(t) for t in a specified interval, then subdividing the curve amounts to subdividing the interval. The implicit function meshes well with GPU parallelism over a triangle containing the curve or a part thereof: For each pixel in the triangle, the same function can be rapidly computed to determine whether the point is on the curve (when f(x, y)=0), is on one side of the curve (when f(x, y)>0), or is on the other side of the curve (when f(x, y)<0). Thus, the implicit function allows a shader program to direct a GPU to render regions bounded by a curve.
Long before the advent of computer graphics, it was known to piece-wise approximate a curve by means of more-elementary curves. For example, a trigonometric function can be approximated (over a certain range of inputs) by means of a polynomial, whose computation requires only multiplication and addition. For the purposes of computer graphics, polynomials of degree greater than three are generally not used, since the additional computational expense is disproportionate to the visual benefits.
Bézier curves are a particularly important tool for (piece-wise) approximating a desired curve in computer graphics. A Bézier curve is defined geometrically by a sequence of control points; such a sequence is termed herein the “control sequence” of the curve. The curve begins at the first control point (the “initial endpoint”), ends at the last control point (the “terminal endpoint”), and is contained in the convex hull of all the control points. (The convex hull of a set of points is the smallest convex set containing that set of points. A set is convex if for any two points contained in the set, the line segment between the two points lies entirely in the set.) Control points in the control sequence other than endpoints are termed herein “attraction points” since they “attract” the curve toward them. Attraction points are often not on the curve. But an attraction point may be co-incident with an endpoint (and therefore on the curve). Attraction points may also be co-incident with each other. Even if an attraction point is co-incident with another control point, it still has an influence on the shape of the curve. Therefore, repeated control points in the control sequence for a Bézier curve are not superfluous. The ordering of control points in a control sequence is also crucial; the curve defined by control sequence E1, G, H, E2 will look very different from that defined by E1, H, G, E2. Furthermore, endpoints E1 and E2 can also be co-incident, in which case the curve begins and ends at the same location, forming a loop.
A Bézier curve is defined algebraically by a parametric equation, where the parameter runs from 0 at the initial endpoint to 1 at the terminal endpoint. This disclosure is only concerned with Bézier curves of order at most three; consequently, there will be no more than four control points in total. The curve will have degree at most three when there are a total of four control points, degree at most two when there are three control points. This disclosure is not concerned with Bézier curves whose control points are all co-linear, in which case the “curve” is a straight line segment, as there are more efficient techniques than Bézier curves for modeling and rendering straight lines and regions bounded by straight lines.
The ubiquity of Bézier curves for specifying graphics and the advantages of using implicit rather than parametric characterizations of curves for rendering graphics using a GPU have led to attempts to express Bézier curves by means of implicit functions.
Loop and Blinn (Charles Loop and Jim Blinn, “Resolution Independent Curve Rendering using Programmable Graphics Hardware,” in ACM Transactions on Graphics, vol. 24, no. 3 (July) 2005, 1000-1009) have developed an implicit representation of a cubic Bézier curve for use by a shader program. Although the representation admits of very efficient computation by the GPU, the complex procedure for obtaining the representation is computationally expensive. In other words, there is a trade off between the efficiency achieved in the rendering phase and the time spent pre-processing in order to set up that efficient rendering.
Floater (M. S. Floater, “Rational Cubic Implicitization,” in Mathematical Methods for Curves and Surfaces, M. Daehlen, T. Lyche, and L. L. Schumaker, eds., Vanderbilt University Press, Nashville, 1995, pp. 151-159) has developed an alternative implicit representation of a cubic Bézier curve. However, it is not useable by a shader program.
Thus, there is a need for a method of rendering regions bounded by Bézier curves having at most four control points, based on an implicit expression that is compact and can be computed efficiently by a shader program, yet requires few preparatory computations.
similar reference numerals may have been used in different figures to denote similar components.